package demo3;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-07-02
 * Time: 17:37
 */
public class TestDemo3 {


    public static int merge(int[] arr,int left ,int mid,int right){
        int b1 = left;
        int e1 = mid;
        int b2 = mid+1;
        int e2 = right;
        int[] tmp = new int[right-left+1];
        int ans = 0;
        int k = tmp.length-1;
        //  3 5 6 8    1 2 3 5
        while(e1>=b1&&e2>=b2){
            ans += arr[e1]>arr[e2]?(e2-b2+1):0;
            tmp[k--] = arr[e1]>arr[e2]?arr[e1--]:arr[e2--];
        }
        while(e1>=left){
            tmp[k--] = arr[e1--];
        }
        while(e2>=b2){
            tmp[k--] = arr[e2--];
        }
        //拷贝回数组
        for(int i =0;i<tmp.length;++i){
            arr[left+i] = tmp[i];
        }
        return ans;
    }

    public static int process(int[] arr,int left,int right){
        if(left>=right) return 0;
        int mid = left+((right-left)>>>1);
        return process(arr,left,mid)+process(arr,mid+1,right)
                +merge(arr,left,mid,right);
    }

    public static int reversePairs(int[] arr){
       return  process(arr,0,arr.length-1);
    }

    public static void main(String[] args) {
        int[] arr = {6,5,9,8,6,2};
        // 2 + 1 + 3+ 2 + 1=9个逆序对
        System.out.println(reversePairs(arr));
    }

}
